/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    // vector<int> postorderTraversal(TreeNode * root) {
    //     vector<int> result;
    //     traverse(root, result);
    //     return result;
    // }
    // void traverse(TreeNode * root, vector<int>& result)
    // {
    //     if (!root)
    //     {
    //         return;
    //     }
    //     traverse(root->left, result);
    //     traverse(root->right, result);
    //     result.push_back(root->val);
    // }
    
    vector<int> postorderTraversal(TreeNode * root) {
        vector<int> result;
        stack<TreeNode *> s;
        TreeNode * pre; // 防止重复访问
        if (!root)
        {
            return result;
        }
        while (root || !s.empty())
        {
            while (root)
            {
                s.push(root);
                root = root->left;
            }
            root = s.top();
            if (!root->right || root->right == pre)
            {
                result.push_back(root->val);
                s.pop();
                pre = root;
                root = NULL; //重要，不要再添加下去了
            }
            else
            {
                root=root->right;
            }
        }
        return result;
    }
    
    // 法三：翻转数组/逆序添加（但是注意不是和前序或中序相反）
    //  vector<int> postorderTraversal(TreeNode * root) {
    //     vector<int> result;
    //     stack<TreeNode *> s;
    //     if (!root)
    //     {
    //         return result;
    //     }
    //     s.push(root);
    //     while (!s.empty())
    //     {
    //         root = s.top();
    //         s.pop();
    //         result.insert(result.begin(), root->val);
    //         if (root->left) s.push(root->left);
    //         if (root->right) s.push(root->right);
    //     }
    //     return result;
    // }
};